package DynamicProgrammingPackage;

public class robII_ {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 3, 2}));
    }

    // 1. dp[j] 表示考虑偷下标j所得的最大金额
    // 2. 递推公式: dp[j] = Math.max(dp[j - 2] + nums[j],dp[j - 1])
    // 3. 初始化: dp[0] = nums[0]
    // 4. 遍历顺序: 从前向后遍历
    // 成环, 可以将分成三种情况
    // 1. 考虑偷0 不考虑偷尾
    // 2. 考虑偷尾 不考虑偷0
    // 3. 0和尾都不考虑
    // 1.2 包含了3
    public static int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }

        // dp1为考虑偷0
        // dp2为考虑偷尾
        int[] dp1 = new int[nums.length];
        int[] dp2 = new int[nums.length];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        dp2[1] = nums[1];
        for(int j = 2 ; j < nums.length ; j++){
            dp1[j] = Math.max(dp1[j - 2] + nums[j], dp1[j - 1]);
            dp2[j] = Math.max(dp2[j - 2] + nums[j], dp2[j - 1]);
        }
        return Math.max(dp1[nums.length - 2], dp2[nums.length - 1]);
    }
}
